#ifndef PQUEUE_H
#define PQUEUE_H

#include <vector>
#include <functional>
using std::vector;
using std::less;

template <typename DT, typename FT = less<DT> > class PQueue {
private:
    typedef typename vector<DT>::iterator PQVit;
    typedef typename vector<DT>::reverse_iterator PQVrit;
    vector<DT> pqv;
public:
    PQueue(FT cmp = less<DT>{}): cmp(cmp){ }
    void make_heap(void);
    void up_fix_heap(int idx);
    void down_fix_heap(int idx);
    void push(DT const &data); //保持堆序地压入
    void pop(void);
    DT &top(void) { return pqv[0]; }
    DT dequeue(void);
    void pop_back(void) { pqv.pop_back(); }
    void push_back(DT const &data) { pqv.push_back(data); };
    void clear(void) { pqv.clear(); }
    bool empty(void) { return pqv.empty(); }
    int size(void){ return pqv.size(); } 
    PQVit begin(void) { return pqv.begin(); }
    PQVit end(void) { return pqv.end(); }
    PQVrit rbegin(void) { return pqv.rbegin(); }
    PQVrit rend(void) { return pqv.rend(); }
private:
    FT cmp; 
};


template <typename DT, typename FT> 
DT PQueue<DT, FT>::dequeue(void) {
    DT md = pqv[0];
    pop();
    return md;
}

template <typename DT, typename FT> 
void PQueue<DT, FT>::pop(void) {
    pqv.resize(pqv.size()-1);
    pqv[0] = pqv[pqv.size()];
    down_fix_heap(0);
}

template <typename DT, typename FT> 
void PQueue<DT, FT>::push(DT const &data) {
    pqv.push_back(data);
    up_fix_heap(pqv.size()-1);
}

template <typename DT, typename FT> 
void PQueue<DT, FT>::up_fix_heap(int idx) {
    DT tmp = pqv[idx];
    while(idx>0) {
        int par = (idx-1)/2;
        if(cmp(pqv[par], tmp)) break;
        pqv[idx] = pqv[par];
        idx = par;
    }
    pqv[idx] = tmp;

}
template <typename DT, typename FT> 
void PQueue<DT, FT>::down_fix_heap(int idx) {
    int lc = idx*2+1;
    int rc;
    int midx;
    while(lc < pqv.size()) {
        midx = idx;
        if(cmp(pqv[lc], pqv[midx])) {
            midx = lc;
        }
        rc = lc+1;
        if(rc<pqv.size() && cmp(pqv[rc], pqv[midx])) {
            midx = rc;
        }
        if(idx == midx) break;
        DT tmp = pqv[idx];
        pqv[idx] = pqv[midx];
        pqv[midx] = tmp;
        idx = midx;
        lc = idx*2+1;
    }
        

}

template <typename DT, typename FT> 
void PQueue<DT, FT>::make_heap(void) {
    int idx =  pqv.size()/2-1; //(pqv.size()-1-1)/2 
    while(idx>=0) {
        down_fix_heap(idx);
        idx--;
    }

}

#endif //PQUEUE_H
